/**
 * 给定一个数组与一个target
 * 要求[1...target]所有数值都能由数组的子序列和得到
 * 问最少要往数组里添加几个数
 * 贪心，假设已经可以得到[1...level]的数，且当前未用的最小元素是x，
 * 如果 level + 1 < x， 则 level + 1 必然不能得到，因此需要插入一个数
 * 如果 level + 1 >= x，则用掉x以后，可以得到 [1... level+x] 区间
 */
class Solution {
public:
    int minimumAddedCoins(vector<int>& coins, int target) {
        std::priority_queue<int, vector<int>, greater<int>> q;
        for(auto i : coins) q.push(i);

        int n = coins.size();
        int ans = 0;
        int level = 0;
        int last = -1;
        while(level < target){
            if(not q.empty() and (last = q.top()) <= level + 1){
                q.pop();
                level += last;
            }else{
                q.push(level + 1);
                ++ans;
            }
        }
        return ans;
    }
};